The present invention relates to data compression and data decompression. More particularly, the present invention relates to lossless data compression and decompression.
A lossless data compression/decompression refers to the use of data compression/decompression algorithms that enable original data to be reconstructed from compressed data. Lossless data compression/decompression is used in a many of applications. For example, lossless data compression/decompression is used in the popular Winzip® application and Unix® gzip (GNU zip) application. Especially, lossless data compression/decompression is used when it is important that an original data and a decompressed data be identical.
A traditional solution for the lossless data compression/decompression uses a dynamic dictionary technique. The dynamic dictionary technique refers to creating a dictionary (i.e., an object such as a list, an array, a vector storing words and/or their references) dynamically, on the fly, while examining contents of input data to be compressed. Larger input data on an average includes more repeating symbols than smaller input data, as probability of finding repeating symbols in the larger input data stream is higher than the smaller input data. Therefore, larger input data become compressed more efficiently than small input data on an average when using the dynamic dictionary based technique. However, having larger input data is a disadvantage when used in a conjunction with a cache memory, as larger data blocks impact cache performance. It has been proven that data blocks are compressed better when they are 512 bytes or larger, however a typical cache memory has a block length of 32 to 128 bytes.
Though the traditional solution performs lossless data compression/decompression well, there are ways to further improve compression efficiency and compression speed of the traditional solution. Thus, it is desirable to provide a system and method to perform lossless data compression/decompression efficiently and fast.